package _01_sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author: mornd
 * @dateTime: 2023/6/23 - 10:32
 * 计数排序 (优化后可以处理负数) O(2n + k) 比其他排序要快 O(n*log n)
 */
public class CountingSortPositive {
    @Test
    public void test() {
        int[] arr = {3, 1, 2, -2, -1};
        countingSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private void countingSort(int[] arr) {
        //  1、找到数组最大元素
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            max = Math.max(arr[i], max);
            min = Math.min(arr[i], min);
        }
        // 新建数组记录出现元素的个数
        int[] countArr = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i] - min]++;
        }
        // 3、根据新数组的索引及索引值，组成有序的数组
        for (int i = 0, j = 0; i < countArr.length; i++) {
            while (countArr[i] > 0) {
                arr[j++] = i + min;
                countArr[i]--;
            }
        }
    }
}
